from queue import Queue

def lewko_waters(root):
    c, max_len, m = 1, 1, []
    q = Queue()
    root.attr = [1]
    q.put(root)
    while not q.empty():
        tmp = q.get()
        v = tmp.attr
        max_len = max(max_len, len(v))
        if tmp.is_leaf():
            m.append(tmp.attr)
            continue
        lc, rc = tmp.children[0], tmp.children[1]
        if tmp.gate.k == 1:
            lc.attr = v
            rc.attr = v
        else:
            v += [0] * (c - len(v))
            lc.attr = [0] * c + [-1]
            rc.attr = v + [1]
            c += 1
        q.put(lc)
        q.put(rc)
    for row in m:
        row += [0] * (max_len - len(row))
    return m

def liu_cao_wong():
    pass
